class Solution:
    def maxProfit(self, k: int, prices: list) -> int:
        def getProfit1():
            buy = -2**31
            sell = 0
            for i in range(len(prices)):
                buy = max(buy, sell - prices[i])
                sell = max(sell, buy + prices[i])

            return sell

        def getProfit2():
            buy = [-2**31 for _ in range(k + 1)]
            sell = [0 for _ in range(k + 1)]
            pre_buy = [-2**31 for _ in range(k + 1)]
            pre_sell = [0 for _ in range(k + 1)]
            for i in range(1, len(prices) + 1):
                for j in range(1, k + 1):
                    buy[j] = max(pre_buy[j], sell[j - 1] - prices[i - 1])
                    sell[j] = max(pre_sell[j], buy[j] + prices[i - 1])
                    pre_buy[j] = buy[j]
                    pre_sell[j] = sell[j]

            return sell[-1]

        return getProfit1() if k >= len(prices) else getProfit2()
